/*
 * KMP.h
 *
 *  Created on: 2008-12-2
 *      Author: Ocsik
 */

#ifndef KMP_H_
#define KMP_H_
#include <string>
using std::string;

class Assert{};

int * Max_Prefix_Substring(string Pattern)
{
	int * K;
	unsigned int length = Pattern.size();
	K = new int[length];
	K[0] = 0;
	for(unsigned int i=0; i<length; i++)
	{
		int k = K[i];
		while(k>0 && Pattern[i+1] != Pattern[k])
			k = K[k-1];
		if(Pattern[i+1] == Pattern[k])
			K[i+1] = k+1;
		else
			K[i+1] = 0;
	}
	return K;
}

int KMP(string Pattern, string Target)
{
	unsigned int t_length = Target.size();
	unsigned int p_length = Pattern.size();
	int * K = new int[p_length];
	K = Max_Prefix_Substring(Pattern);
	unsigned int p_index = 0;	//index for pattern
	unsigned int t_index;	//index for target
	for(t_index=0; t_index<t_length; t_index++)
	{
		while(Pattern[p_index] != Target[t_index] && p_index>0)
			p_index = K[p_index-1];
		if(Pattern[p_index] == Target[t_index])
			p_index++;
		if(p_index == p_length)
			return(t_index - p_index + 1);
	}
	return (-1);
}

#endif /* KMP_H_ */
